package problem;

import java.util.*;

/**
 * @author RunningShrimp
 * @date 2021/5/10  20:56
 * @see <a href="https://leetcode-cn.com/problems/leaf-similar-trees/">872. 叶子相似的树</a>
 * 测试用例：
 * [3,5,1,6,7,4,2,null,null,null,null,null,null,9,11,null,null,8,10]
 * [3,5,1,6,2,9,8,null,null,7,4]
 */

public class LeafSimilarTree {
    /**
     * 广度优先遍历（辅助栈）
     * @param root1
     * @param root2
     * @return
     */
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        Queue<Integer> numQueueRoot1 = traversal(root1);
        Queue<Integer> numQueueRoot2 = traversal(root2);
        if (numQueueRoot1.size() != numQueueRoot2.size()) {
            return false;
        } else {
            while (!(numQueueRoot1.isEmpty() && numQueueRoot2.isEmpty())) {
                if (!Objects.equals(numQueueRoot1.poll(), numQueueRoot2.poll())) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 深度优先遍历
     * @param root
     * @return
     */
    private Queue<Integer> traversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        Queue<Integer> numQueue = new ArrayDeque<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                if (node.left == null && node.right == null) {
                    numQueue.add(node.val);
                }
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                node = node.right;
            }
        }
        return numQueue;
    }

    /**
     * 递归遍历
     * @param root1
     * @param root2
     * @return
     */
    public boolean leafSimilarPost(TreeNode root1, TreeNode root2) {
        Queue<Integer> numQueueRoot1 =new ArrayDeque<>();
        Queue<Integer> numQueueRoot2 = new ArrayDeque<>();

        postOrderTraversal(root1,numQueueRoot1);
        postOrderTraversal(root2,numQueueRoot2);

        if (numQueueRoot1.size() != numQueueRoot2.size()) {
            return false;
        } else {
            while (!(numQueueRoot1.isEmpty() && numQueueRoot2.isEmpty())) {
                if (!Objects.equals(numQueueRoot1.poll(), numQueueRoot2.poll())) {
                    return false;
                }
            }
        }

        return true;
    }
    private void postOrderTraversal(TreeNode node, Queue<Integer> queue){
        if(node == null){
            return;
        }
        postOrderTraversal(node.left,queue);
        postOrderTraversal(node.right,queue);
        if(node.left==null&&node.right==null){
            queue.add(node.val);
        }
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
